1. Field of the Invention
The invention relates to encryption techniques for data security, and more particularly to a system for distributing a public key for network users to share a secret key through the use of a public key, a public key encryption system such as an El-Gamal type encryption system for network users to make a mutual secret communication through the use of a public key, and an El-Gamal type verification system, which is one of electronic signature systems, for network users to verify a correspondence and/or a transmitter, and apparatuses for operating a bivector, to be used for those systems, such as an apparatus for multiplying a bivector by an integer.
2. Description of the Related Art
Various techniques belonging to a public key encryption system wherein secret communication is made in open network base security thereof on difficulty in solving an issue of a discrete logarithm in a finite field GF(p).
For instance, a system of distributing DH type public key having been suggested by W. Diffie and M. Hellman, New directions in cryptography, IEEE, Trans. Inf. Theory, IT-22, 6, pp. 644-654, and El-Gamal cryptography and signature systems having been suggested by T. E. El-Gamal, A public key cryptosystem and a signature scheme based on discrete logarithm, Proc. Crypto 84, 1984, base security thereof on that an issue of a discrete logarithm in a finite field GF(p) is quite difficult to solve.
Hereinbelow is explained the issue of a discrete logarithm in a finite field GF(p). It is now supposed that p indicates a prime number, and that GF(p) operates an integer N equal to or greater than 0, but smaller than p (N=0, 1, 2, - - - , pxe2x88x921), with the prime number being used as a modulo. It is also supposed that the following equation is established.
Y=xcex1X mod p (1xe2x89xa6Xxe2x89xa6pxe2x88x921)
In the equation, a indicates xcex1 certain fixed primitive root of GF(p). That is, elements of GF(p), 1, 2 - - - , pxe2x88x921, other than 0 can be represented in the form of xcex1K where K indicates a certain number. Under those suppositions, X is called a logarithm of Y in GF(p) with the prime number p acting as a base.
It is easy to calculate Y on the basis of X. Specifically, what is required to do so is to merely conduct multiplication by the number of 2xc3x97log2X. To the contrary, it is quite difficult to calculate X on the basis of Y, even if there would be employed an algorithm which is best among presently known algorithms. An amount of calculation for obtaining X on the basis of Y is almost the same as an amount of calculation for prime factor factorization of a composite number having almost the same magnitude as that of the prime number p. A difficulty in calculating X on the basis of Y is called a discrete logarithm problem.
In accordance with the above-mentioned DH type public key distribution system, a first user A and a second user B can share a common key K, which is secret data, with the common key K being kept secret to others, even though open network is utilized. This is based on that the above-mentioned discrete logarithm problem is quite difficult to solve.
A prime number p and a primitive root xcex1 are in advance informed to others as open data. The first user A randomly selects an integer XA in the range of 0 and (pxe2x88x921), and the thus selected integer XA is kept secret. Similarly, the second user B randomly selects an integer XB in the range of 0 and (pxe2x88x921), and the thus selected integer XB is kept secret. The first user A calculates the following equation.
YA=xcex1XA mod p (1xe2x89xa6YAxe2x89xa6pxe2x88x921)(xe2x80x9cXAxe2x80x9d means xe2x80x9cXAxe2x80x9d. The same applies to xe2x80x9cXBxe2x80x9d, xe2x80x9cXUxe2x80x9d etc., hereinbelow.)
Then, the first user A transmits a calculation result YA to the second user B. Similarly, the second user B calculates the following equation.
YB=xcex1XB mod p (1xe2x89xa6YBxe2x89xa6pxe2x88x921)
Then, the second user B transmits a calculation result YB to the first user A.
After the calculation results YA and YB have been exchanged, the first user A calculates the common key K, as follows.
K=YBXA mod p=(xcex1XB mod p)XA mod p=xcex1XAXB mod p (1xe2x89xa6Kxe2x89xa6pxe2x88x921)
Similarly, the second user B calculates the common key K, as follows.
K=YAXB mod p=(xcex1XA mod p)XB mod p=xcex1XAXB mod p (1xe2x89xa6Kxe2x89xa6pxe2x88x921)
Thus, the first and second users A and B can share the common key K (K=xcex1XAXB mod p) in secret.
Thereafter, the first and second users A and B can make secret communication therebetween through the use of the common key K. In the above-mentioned procedure, only the calculation results YA and YB are on open network. Since it would be necessary to solve the discrete logarithm problem in order to obtain the integers XA and XB both of which are secret data, a third party cannot know the common key K on the premise that the discrete logarithm problem is quite difficult to solve.
In accordance with the above-mentioned El-Gamal encryption system, it is possible to make a secret communication on open network as follows, based on the fact that the discrete logarithm problem is difficult to solve.
A prime number p and a primitive root xcex1 are in advance informed to others as open data. Each of users U randomly selects an integer XU, and the thus selected integer XU is kept secret. In addition, each of users U calculates the following equation.
YU=xcex1XU mod p (1xe2x89xa6YUxe2x89xa6pxe2x88x921)
Then, each of users U transmits the calculation result YU to other users as a public key.
Herein, it is supposed that a first user A transmits a correspondence M to a second user B in secret. First, the first user A makes the following ciphers C1 and C2 through the use of a random number K which only the first user A knows, and a public key YB of the second user B.
C1=xcex1K mod p
C2=Mxc3x97YBK mod p
Then, the first user A transmits the ciphers C1 and C2 to the second user B. The second user B having received the ciphers can obtain the correspondence M by calculating the following equation through the use of an integer XB which only the second user B knows.
M=C1xe2x88x92XBxc3x97C2 mod p
In the above-mentioned El-Gamal encryption system, only the ciphers C1 and C2 are on open network. Since it would be necessary to solve the discrete logarithm problem in order to obtain the random number K and the correspondence M both of which are secret data, a secret communication can be made on the premise that the discrete logarithm problem is quite difficult to solve.
In accordance with the above-mentioned El-Gamal signature system, electronic signature can be accomplished as follows, based on the fact that it is quite difficult to solve the discrete logarithm problem.
A prime number p and a primitive root xcex1 are in advance informed to others as open data. A certifier U randomly selects an integer XU as a signature key, and the thus selected integer XU is kept secret. In addition, the certifier U calculates the following equation.
YU=xcex1XU mod p (1xe2x89xa6YUxe2x89xa6pxe2x88x921)
Then, the certifier U discloses the calculation result YU to others as a verification key.
Herein, it is supposed that a verifier V verifies a signature made to a correspondence M of the certifier U. First, the certifier U makes the following signatures R and S through the use of a random number K which only the certifier knows, and a signature key XU of the certifier U itself.
xe2x80x83R=xcex1K mod p
S=(M=XUxc3x97R)xc3x97Kxe2x88x921 mod p
Then, the certifier U transmits a correspondence M together with the signatures R and S to the verifier V. The verifier V having received the signatures R and S verifies whether the following equation is established through the use of a verification key Yu of the certifier U.
xcex1M=YuRxc3x97RS mod p
In the above-mentioned El-Gamal signature system, only the correspondence M and the signatures R and S are on open network. Since it would be necessary to solve the discrete logarithm problem in order to obtain the signature key XU which is secret data, it would be quite difficult or almost impossible for a person other than the certifier U to impersonate the certifier U, and hence, electronic signature can be accomplished on the premise that the discrete logarithm problem is quite difficult to solve.
As having been explained so far, most of the public key encryption systems base its security on the fact that the discrete logarithm problem in a finite field GF(p) is difficult to solve. However, recent development in a super computer and various arithmetic algorithms is making it possible to solve the discrete logarithm problem in a finite field GF(p) with a relatively small amount of calculation.
As a countermeasure thereto, it is recommended to employ a prime number p having 1024 bit, namely, having an order of about 300 or greater in decimalism. However, it would be necessary to prepare a large-scale circuit for finite field operation in order to make an operation on a finite field GF(p), using a prime number p having about 300 or more orders. This prevents various techniques in a public key encryption system from being put to practical use.
It is an object of the present invention to provide an apparatus for making an operation, to be used for an encryption system, and other various techniques for accomplishing a public key encryption system in a smaller scale.
As having been explained, the conventional public key encryption systems are based on the fact that it is quite difficult or almost impossible to solve the discrete logarithm problem of a finite field, more accurately, of multiplicative group of a finite field. The principle of the present invention is that Jacobian group of algebraic curves in a finite field is employed in place of multiplicative group a finite field.
Hereinbelow is explained Jacobian group of algebraic curves. Any algebraic curve has a characteristic comprised of a positive integer called a genus. It is now supposed that a curve C has a genus G. It is now possible to define an addition among a set of any G number of points on the curve C, as follows. There are defined following two sets X1 and X2 each composed of the G number of points on the curve C.
X1={P11, P12, - - - , P1G}
X2={P21, P22, - - - , P2G}
A curve B is defined as a curve having the smallest degree among curves passing all points belonging to the sets X1 and X2. The thus defined curve B intersects with the curve C at another G number of points as well as points belonging to the sets X1 or X2. Another number of points are defined as Q1, Q2, - - - , QG. Herein, a curve A is defined as a curve having the smallest degree among curves passing through all the G number of points, Q1, Q2, - - - , QG. Thus defined curve A intersects with the curve C at another G number of points, R1, R2, - - - , RG as well as the G number of points, Q1, Q2, - - - , QG. An addition of the sets X1 and X2 makes Y={R1, R2, - - - , RG}.
A set of any G number of points on the curve C wherein an addition is defined as mentioned above is called Jacobian group of the curve C in a finite field GF(p). A number of elements of Jacobian group, namely, a number of sets each composed of any G number of points on the curve C is equal to about pG. An arithmetically detailed explanation is made, for instance, by J. H. Silverman, The Arithmetic of Elliptic Curves, Springer-Verlag, 1986.
In order to accomplish various techniques belonging to a public key encryption system, which have sufficient strength with respect to cryptography, it is necessary to use a group having a sufficient number of element, even if multiplicative group in a finite field or Jacobian group of algebraic curves were employed. Generally, a number of elements of multiplicative group in a finite field GF(p) is equal to (pxe2x88x921), whereas a number of elements of Jacobian group of algebraic curves having a genus G in a finite field GF(p) is equal to about pG. Accordingly, if Jacobian group of algebraic curves having a genus G in a finite field is employed in place of multiplicative group of a finite field, it would be possible to make an order of p in a finite field GF(p) about 1/G smaller than an order of p obtained when multiplicative group of a finite field is employed, on the assumption that a strength with respect to cryptography is kept at the same level, namely, a number of elements in groups to be used is kept almost the same.
Thus, various techniques of a public key encryption system in accordance with the present invention make it possible to employ a smaller-sized finite field without reduction in a strength with respect to cryptography, which ensures that a sufficient strength with respect to cryptography can be accomplished by means of a smaller-sized apparatus at less costs.
Specifically, the present invention provides the following apparatuses and recording mediums.
In one aspect of the present invention, there is provided an apparatus for summing double vectors (alternatively referred to as bivectors) each having a plurality of pairs of elements selected from a predetermined finite field, the apparatus including (a) a device for inputting double vectors X1 and X2, and a parameter A for defining a curve therethrough, (b) a first storage memory for storing the double vectors X1 therein, (c) a second storage memory for storing the double vectors X2 therein, (d) a third storage memory for storing the parameter A therein, and (e) a device for reading the double vectors X1 and X2, and the parameter A out of the first, second and third storage memories, respectively, and, when the double vectors X1 and X2 are coordinate value rows of points in point-sets Q1 and Q2 on the curve defined with the parameter A, respectively, operating a double vectors X3 comprised of coordinate value row of points in a point-set Q3 equal to a sum of the point-sets Q1 and Q2 in Jacobian group of the curve defined with the parameter A.
There is further provided an apparatus for summing bivectors each having a plurality of pairs of elements selected from a predetermined finite field, the apparatus including (a) a device for inputting bivectors X1 and X2, and a parameter A for defining a curve therethrough, (b) a first storage memory for storing the bivector X1 therein, (c) a second storage memory for storing the bivector X2 therein, (d) a third storage memory for storing the parameter A therein, and (e) a union-set operating device for reading the bivectors X1 and X2, and the parameter A out of the first, second and third storage memories, respectively, and, when the bivectors X1 and X2 are supposed to be coordinate value rows of points in point-sets on the curve defined with the parameter A, respectively, operating a bivector T1 comprised of coordinate value row of points in a union-set of the point-sets indicated by X1 and X2, (f) a fourth storage memories for storing the bivector T1 operated by the union-set operating device, (g) a first point-set operating device for reading the bivector T1 out of the fourth storage memory, and the parameter A out of the third storage memory, and, when the bivector T1 is supposed to be coordinate value row of points on the curve defined with the parameter A, operating a bivector T2 comprised of coordinate value row of points in a point-set indicative of inverse of the point-set expressed by T1 in Jacobian group of the curve defined with the parameter A, (h) a fifth storage memory for storing the bivector T2 operated by the first point-set operating device, (i) a second point-set operating device for reading the bivector T2 out of the fifth storage memory, and the parameter A of the third storage memory, and, when the bivector T2 is supposed to be coordinate value row of pints on the curve defined with the parameter A, operating a bivector X3 comprised of coordinate value row of points in a point-set indicative of inverse of the point-set expressed by T2 in Jacobian group of the curve defined with the parameter A, and (j) a device for outputting the bivector X3 operated by the second point-set operating device.
The above-mentioned apparatus may further include (k) a sixth storage memory for storing a parameter B therein, and (l) a seventh storage memory for storing a bivector S1 therein, and wherein the first point-set operating device includes (g-1) a common curve operating device for reading the bivector T1 out of the fourth storage memory, and the parameter A out of the third storage memory, and, when the bivector T1 is supposed to be coordinate value row of points on the curve defined with the parameter A, operating a parameter B of a curve passing through all points constituting the point-sets expressed by T1, (g-2) an intersection-set operating device for reading the parameter B out of the sixth storage memory, and the parameter A out of the third storage memory, and operating a bivector S1 comprised of coordinate value row of points in an intersection between a curve defined with the parameter A and a curve defined with the parameter B, (g-3) a difference-set operating device for reading the bivector T1 out of the fourth storage memory, and the bivector S1 out of the seventh storage memory, and, when the bivectors T1 and S1 are supposed to be coordinate value rows of points on the curve defined with the parameter A, respectively, operating the bivector T2 comprised of coordinate value row of points in a point-set obtained by subtracting a point-set indicated by the bivector T1 from a point-set indicated by the bivector S1, and (g-4) a device for outputting the bivector T2 operated by the difference-set operating device.
It is preferable that the above-mentioned apparatus may further include (k) an eighth storage memory for storing a parameter C therein, and (l) a ninth storage memory for storing a bivector S2 therein, and wherein the second point-set operating device includes (i-1) a common curve operating device for reading the bivector T2 out of the fifth storage memory, and the parameter A out of the third storage memory, and, when the bivector T2 is supposed to be coordinate value row of points on the curve defined with the parameter A, operating a parameter C of a curve passing through all points indicated by T2, (i-2) an intersection-set operating device for reading the parameter C out of the eighth storage memory, and the parameter A out of the third storage memory, and operating a bivector S2 comprised of coordinate value row of points in an intersection between a curve defined with the parameter A and a curve defined with the parameter C, (i-3) a difference-set operating device for reading the bivector T2 out of the fifth storage memory, and the bivector S2 out of the ninth storage memory, and, when the bivectors T2 and S2 are supposed to be coordinate value rows of points on the curve defined with the parameter A, respectively, operating the bivector X3 comprised of coordinate value row of points in a point-set obtained by subtracting a point-set indicated by the bivector T2 from a point-set indicated by the bivector S2, and (i-4) a device for outputting the bivector X3 operated by the difference-set operating device.
In another aspect of the present invention, there is provided a recording medium readable by a computer, storing a program therein for causing a computer to act as an apparatus for summing bivectors each having a plurality of pairs of elements selected from a predetermined finite field, the apparatus including (a) a device for inputting bivectors X1 and X2, and a parameter A for defining a curve therethrough, (b) a first storage memory for storing the bivector X1 therein, (c) a second storage memory for storing the bivector X2 therein, (d) a third storage memory for storing the parameter A therein, and (e) a device for reading the bivectors X1 and X2, and the parameter A out of the first, second and third storage memories, respectively, and, when the bivectors X1 and X2 are supposed to be coordinate value rows of points in point-sets Q1 and Q2 on the curve defined with the parameter A, respectivley, operating a bivector X3 comprised of coordinate value row of points in a point-set Q3 equal to a sum of the point-sets Q1 and Q2 in Jacobian group of the curve defined with the parameter A.
There is further provided a recording medium readable by a computer, storing a program therein for causing a computer to act as an apparatus for summing bivectors each comprising a plurality of pairs of elements selected from a predetermined finite field, the apparatus including (a) a device for inputting bivectors X1 and X2, and a parameter A for defining a curve therethrough, (b) a first storage memory for storing the bivector X1 therein, (c) a second storage memory for storing the bivector X2 therein, (d) a third storage memory for storing the parameter A therein, and (e) a union-set operating device for reading the bivectors X1 and X2, and the parameter A out of the first, second and third storage memories, respectively, and, when the bivectors X1 and X2 are supposed to be coordinate value rows of points on the curve defined with the parameter A, operating a bivector T1 comprised of coordinate value row of points in a union-set of the point-sets indicated by X1 and X2, (f) a fourth storage memory for storing the bivector T1 operated by the union-set operating device, (g) a first point-set operating device for reading the bivector T1 out of the fourth storage memory, and the parameter A out of the third storage memory, and, when the bivector T1 is supposed to be coordinate value row of points on the curve defined with the parameter A, operating a bivector T2 comprised of coordinate value row of points in a point-set indicative of inverse of the point-set indicated by T1 in Jacobian group of the curve defined with the parameter A, (h) a fifth storage memory for storing the bivector T2 operated by the first point-set operating device, (i) a second point-set operating device for reading the bivector T2 out of the fifth storage memory, and the parameter A out of the third storage memory, and, when the bivector T2 is supposed to be coordinate value row of points on the curve defined with the parameter A, operating a bivector X3 comprised of coordinate value row of points in a point-set indicative of inverse of the point-set indicated by T2 in Jacobian group of the curve defined with the parameter A, and (j) a device for outputting the bivector X3 operated by the second point-set operating device.
There is still further provided an apparatus for doubling a bivector having a plurality of pairs of elements selected from a predetermined finite field, the apparatus including (a) a device for inputting a bivector X, and a parameter A for defining a curve therethrough, (b) a first storage memory for storing the bivector X therein, (c) a second storage memory for storing the parameter A therein, and (d) a device for reading the bivector X out of the first storage memory, and the parameter A out of the second storage memory, and, when the bivector X is supposed to be coordinate value row of points in a point-set Q on the curve defined with the parameter A, operating a bivector Y comprised of coordinate value row of points in a point-set R equal to a doubled Q in Jacobian group of the curve defined with the parameter A.
There is yet further provided an apparatus for doubling a bivector having a plurality of pairs of elements selected from a predetermined finite field, the apparatus including (a) a device for inputting a bivector X, and a parameter A for defining a curve therethrough, (b) a first storage memory for storing the bivector X therein, (c) a second storage memory for storing a bivector Xa which is a copy of the bivector X, (d) a third storage memory for storing the parameter A therein, (e) a bivector adding device for reading the bivector X out of the first storage memory, the bivector Xa out of the second storage memory, and the parameter A out of the third storage memory, and adding the bivector X to the bivector Xa to thereby have a sum of 2X, and (f) a device for outputting the bivector 2X operated by the bivector adding device.
There is still further provided a recording medium readable by a computer, storing a program therein for causing a computer to act as an apparatus for doubling a bivector having a plurality of pairs of elements selected from a predetermined finite field, the apparatus including (a) a device for inputting a bivector X, and a parameter A for defining a curve therethrough, (b) a first storage memory for storing the bivector X therein, (c) a second storage memory for storing the parameter A therein, and (d) a device for reading the bivector X out of the first storage memory, and the parameter A out of the second storage memory, and, when the bivector X is supposed to be coordinate value row of points in a point-set Q on the curve defined with the parameter A, operating a bivector Y comprised of coordinate value row of points in a point-set R equal to a doubled Q in Jacobian group of the curve defined with the parameter A.
There is yet further provided a recording medium readable by a computer, storing a program therein for causing a computer to act as an apparatus for doubling a bivector including a plurality of pairs of elements selected from a predetermined finite field, the apparatus including (a) a device for inputting a bivector X, and a parameter A for defining a curve therethrough, (b) a first storage memory for storing the bivector X therein, (c) a second storage memory for storing a bivector Xa which is a copy of the bivector X, (d) a third storage memory for storing the parameter A therein, (e) a bivector adding device for reading the bivector X out of the first storage memory, the bivector Xa out of the second storage memory, and the parameter A out of the third storage memory, and adding the bivector X to the bivector Xa to thereby have a sum of 2X, and (f) a device for outputting the bivector 2X operated by the bivector adding device.
There is still yet further provided an apparatus for multiplying a bivector by an integer, the bivector having a plurality of pairs of elements selected from a predetermined finite field, the apparatus including (a) a device for inputting therethrough an integer N, a bivector X, and a parameter A for defining a curve, (b) a first storage memory for storing the integer N therein, (c) a second storage memory for storing the bivector X therein, (d) a third storage memory for storing the parameter A therein, and (e) a device for reading the integer N out of the first storage memory, the bivector X out of the second storage memory, and the parameter A out of the third storage memory, and, when the bivector X is supposed to be coordinate value row of points in a point-set Q on the curve defined with the parameter A, operating a bivector Z comprised of coordinate value row of points in a point-set R equal to the point-set Q multiplied by the integer N in Jacobian group of the curve defined with the parameter A.
There is further provided an apparatus for multiplying a bivector by an integer, the bivector having a plurality of pairs of elements selected from a predetermined finite field, the including (a) a device for inputting therethrough an integer N, a bivector X, and a parameter A for defining a curve, (b) a first storage memory for storing the integer N therein, (c) a second storage memory for storing the bivector X therein, (d) a third storage memory for storing a bivector Y which is a copy of the bivector X, (e) a fourth storage memory for storing a bivector Z therein, (f) a fifth storage memory for storing the parameter A therein, (g) a sixth storage memory for storing an integer R therein, (h) a bivector adding device for summing bivectors, (i) a bivector doubling device for doubling a bivector, (j) a device for reading the integer N out of the first storage memory, calculating a remainder R obtained when the integer N is divided by 2, and storing the thus obtained R in the sixth storage memory, (k) a device for reading the integer N out of the first storage memory, calculating a quotient by dividing the integer N by 2, and storing the thus obtained quotient in the first storage memory as a renewed integer N, (l) a device for reading the integer R out of the sixth storage memory, if the integer R is equal to 1, reading the bivector Y out of the third storage memory, the bivector Z out of the fourth storage memory, and the parameter A out of the fifth storage memory, inputting the bivectors Y and Z and the parameter A into the bivector adding device, calculating a sum of the bivectors Y and Z, and storing the thus calculated sum in the fourth storage memory, and (m) a device for reading the integer N out of the first storage memory, if the thus read-out integer N is greater than 0, reading the bivector Y out of the third storage memory and the parameter A out of the fifth storage memory, inputting the bivector Y and the parameter A into the bivector doubling device, doubling the bivector Y, and storing the thus doubled bivector Y in the third storage memory, and if the integer N is equal to 0, reading the bivector Z out of the fourth storage memory.
There is still further provided a recording medium readable by a computer, storing a program therein for causing a computer to act as an apparatus for multiplying a bivector by an integer, the bivector including a plurality of pairs of elements selected from a predetermined finite field, the apparatus including (a) a device for inputting therethrough an integer N, a bivector X, and a parameter A for defining a curve, (b) a first storage memory for storing the integer N therein, (c) a second storage memory for storing the bivector X therein, (d) a third storage memory for storing the parameter A therein, and (e) a device for reading the integer N out of the first storage memory, the bivector X out of the second storage memory, and the parameter A out of the third storage memory, and, when the bivector X is supposed to be coordinate value row of points in a point-set Q on the curve defined with the parameter A, operating a bivector Z comprised of coordinate value row of points in a point-set R equal to the point-set Q multiplied by the integer N in Jacobian group of the curve defined with the parameter A.
There is still yet further provided a recording medium readable by a computer, storing a program therein for causing a computer to act as an apparatus for multiplying a bivector by an integer, the bivector including a plurality of pairs of elements selected from a predetermined finite field, the apparatus including (a) a device for inputting therethrough an integer N, a bivector X, and a parameter A for defining a curve, (b) a first storage memory for storing the integer N therein, (c) a second storage memory for storing the bivector X therein, (d) a third storage memory for storing a bivector Y which is a copy of the bivector X, (e) a fourth storage memory for storing a bivector Z therein, (f) a fifth storage memory for storing the parameter A therein, (g) a sixth storage memory for storing an integer R therein, (h) a bivector adding device for summing bivectors, (i) a bivector doubling device for doubling a bivector, (j) a device for reading the integer N out of the first storage memory, calculating a remainder R obtained when the integer N is divided by 2, and storing the thus obtained R in the sixth storage memory, (k) a device for reading the integer N out of the first storage memory, calculating a quotient by dividing the integer N by 2, and storing the thus obtained quotient in the first storage memory as a renewed integer N, (l) a device for reading the integer R out of the sixth storage memory, if the integer R is equal to 1, reading the bivector Y out of the third storage memory, the bivector Z out of the fourth storage memory, and the parameter A out of the fifth storage memory, inputting the bivectors Y and Z and the parameter A into the bivector adding device, calculating a sum of the bivectors Y and Z, and storing the thus calculated sum in the fourth storage memory, and (m) a device for reading the integer N out of the first storage memory, if the thus read-out integer N is greater than 0, reading the bivector Y out of the third storage memory and the parameter A out of the fifth storage memory, inputting the bivector Y and the parameter A into the bivector doubling device, doubling the bivector Y, and storing the thus doubled bivector Y in the third storage memory, and if the integer N is equal to 0, reading the bivector Z out of the fourth storage memory.
There is further provided a system for distributing a public key wherein a parameter A defining a curve, and a bivector Q including a plurality of pairs of elements selected from a predetermined finite field are in advance informed of to all users, a user terminal U randomly selects an integer Nu and keeps the thus selected integer Nu secret, a user terminal V randomly selects an integer Nv and keeps the thus selected integer Nv secret, the user terminal U transmits a bivector Qu (Qu=Nuxc3x97Q) to the user terminal V, the bivector Qu being obtained by multiplying the bivector Q by the integer Nu through the use of the integer Nu, the bivector Q, and the parameter A, the user terminal V transmits a bivector Qv (Qv=Nvxc3x97Q) to the user terminal U, the bivector Qv being obtained by multiplying the bivector Q by the integer Nv through the use of the integer Nv, the bivector Q, and the parameter A, the user terminal U multiplies the bivector Qv by the integer Nu through the use of the bivector Qv having been transmitted from the user terminal V, the integer Nu, and the parameter A, to thereby obtain a bivector K (K=Nuxc3x97Qv=Nuxc3x97Nvxc3x97Q) as a common key K, and the user terminal V multiplies the bivector Qu by the integer Nu through the use of the bivector Qu having been transmitted from the user terminal U, the integer Nv, and the parameter A, to thereby obtain a bivector K (K=Nvxc3x97Qu=Nvxc3x97Nuxc3x97Q) as a common key K.
There is further provided a system for distributing a public key, including a center and a plurality of user terminals, the center including (a) a device for receiving a request for a parameter A defining a curve, and a bivector Q including a plurality of pairs of elements selected from a predetermined finite field, and (b) a device for disclosing the bivector Q and the parameter A to a user terminal making a request, the user terminal including (a) a first device for requesting the center to transmit the bivector Q and parameter A both made open, (b) a second device for receiving and retaining the bivector Q and parameter A, and transmitting them to a later mentioned device for multiplying a bivector by an integer, (c) a third device for randomly selecting an integer Nu, keeping the thus selected integer Nu secret, and transmitting the integer Nu to a later mentioned device for multiplying a bivector by an integer, (d) a device for multiplying a bivector by an integer, for receiving the bivector Q and the parameter A from the second device, receiving the integer Nu from third device, and calculating a bivector Qu by multiplying the bivector Q by the integer Nu, (e) a fourth device for transmitting the bivector Qu to other user terminals, (f) a fifth device for receiving a bivector Qv transmitted from other user terminals, and transmitting the bivector Qv to the device, the device receiving the bivector Qv transmitted from the other user terminals, the integer Nu stored in the third device, and the parameter A retained in the second device, and multiplying the bivector Qv by the integer Nu to thereby have a bivector K, and (g) a sixth device for storing the bivector K as a secret key.
There is further provided a recording medium readable by a computer, storing a program therein for accomplishing a system for distributing a public key, the system including a center and a plurality of user terminals, the program causing a computer to act as the center including (a) a device for receiving a request for a parameter A defining a curve, and a bivector Q including a plurality of pairs of elements selected from a predetermined finite field, and (b) a device for disclosing the bivector Q and the parameter A to a user terminal making a request, the program causing a computer to act as the user terminal including (a) a first device for requesting the center to transmit the bivector Q and parameter A both made open, (b) a second device for receiving and retaining the bivector Q and parameter A, and transmitting them to a later mentioned device for multiplying a bivector by an integer, (c) a third device for randomly selecting an integer Nu, keeping the thus selected integer Nu secret, and transmitting the integer Nu to a later mentioned device for multiplying a bivector by an integer, (d) a device for multiplying a bivector by an integer, for receiving the bivector Q and the parameter A from the second device, receiving the integer Nu from third device, and calculating a bivector Qu by multiplying the bivector Q by the integer Nu, (e) a fourth device for transmitting the bivector Qu to other user terminals, (f) a fifth device for receiving a bivector Qv transmitted from other user terminals, and transmitting the bivector Qv to the device, the device receiving the bivector Qv transmitted from the other user terminals, the integer Nu stored in the third device, and the parameter A retained in the second device, and multiplying the bivector Qv by the integer Nu to thereby have a bivector K, and (g) a sixth device for storing the bivector K as a secret key.
There is further provided an El-Gamal type encryption system wherein a parameter A defining a curve, and a bivector Q comprising a plurality of pairs of elements selected from a predetermined finite field are in advance informed of to all users, a user terminal U randomly selects an integer Nu, and keeps the thus selected integer Nu secret, the user terminal U transmits a bivector Qu (Qu=Nuxc3x97Q) to other users as a public key, the bivector Qu being obtained by multiplying the bivector Q by the integer Nu through the use of the integer Nu, the bivector Q, and the parameter A, the user terminal U encrypts a text through the use of the integer Nu and a public key Qv of a user terminal V to which the user terminal U intends to transmit the text, and the user terminal V having received the thus encrypted text decrypts the encrypted text through the use of an integer Nv which the user terminal V retains in secret.
There is further provided an El-Gamal type encryption system including a center and a plurality of user terminals, the center including (a) a first device for receiving public keys disclosed by the user terminals, (b) a second device for receiving a request to transmit a parameter A defining a curve, a bivector Q including a plurality of pairs of elements selected from a predetermined finite field, a public key Qu to a user terminal, and (c) a third device for disclosing the bivector Q, the parameter A, and the public key Qu to the user terminal making the request, when the second means receives the request, the user terminal as a transmitter, including (a) a fourth device for requesting the center to transmit the bivector Q, the parameter A, and the public keys Qv of other user terminals, (b) a fifth device for receiving and retaining the bivector Q, the parameter A, and the public key Qv which have been disclosed by the center in accordance with a request from the fourth means, and transmitting them to a later mentioned first device for multiplying a bivector by an integer, (c) a sixth device for randomly selecting an integer Nu, keeping the thus selected integer Nu secret, and transmitting the integer Nu to a later mentioned first device for multiplying a bivector by an integer, (d) a first apparatus for multiplying a bivector by an integer, for receiving the bivector Q and the parameter A from the second device, receiving the integer Nu from the sixth device, and calculating a bivector Qu by multiplying the bivector Q by the integer Nu, (e) a seventh device for receiving the bivector Qu from the first device, and transmitting the bivector Qu to the center for disclosing as a public key, (f) a second apparatus for selecting a random number Ru and keeping the thus selected random number Ru secret, and transmitting the random number Ru to the first device, the first device receiving the bivector Q transmitted from the second device, the parameter A, and the random number Ru stored in the second apparatus, and multiplying the bivector Q by the random number Ru to thereby have a bivector C1 as a cipher, and storing the thus made cipher in first storage memory, the first apparatus receiving the public key Qv of other user terminals stored in the second device, the parameter A, and the random number Ru, stored in the second apparatus, and multiplying the bivector Qv by the random number Ru to thereby have a bivector T1, and transmitting the thus made bivector T1 to eighth device, (g) an eighth device for calculating a sum t1 of first elements in each of groups included in the bivector T1, and making a cipher C2 to which a correspondence M is added, and (h) a ninth device for cooperating with the eighth means to transmit the ciphers C1 and C2 to other user terminals, the user terminal as a receiver, including (a) a tenth device for receiving and retaining the ciphers C1 and C2 transmitted from the user terminals as a transmitter, the first apparatus receiving the cipher C1, an integer Nv retained in the sixth means, and the parameter A, and calculating a bivector T2 by multiplying the bivector C1 by the integer Nv, and (b) an eleventh device for receiving the cipher C2 and the bivector T2, calculating a sum t2 of first elements in each of groups included in the bivector T2, and decrypting the correspondence M by subtracting the sum t2 from the cipher C2.
There is further provided a recording medium readable by a computer, storing a program therein for accomplishing an El-Gamal type encryption system including a center and a plurality of user terminals, the program causing a computer to act as the center including (a) a first device for receiving public keys disclosed by the user terminals, (b) a second device for receiving a request to transmit a parameter A defining a curve, a bivector Q including a plurality of pairs of elements selected from a predetermined finite field, a public key Qu to a user terminal, and (c) a third device for disclosing the bivector Q, the parameter A, and the public key Qu to the user terminal making the request, when the second device receives the request, the program causing a computer to act as the user terminal as a transmitter, the user terminal including (a) a fourth device for requesting the center to transmit the bivector Q, the parameter A, and the public keys Qv of other user terminals, (b) a fifth device for receiving and retaining the bivector Q, the parameter A, and the public key Qv which have been disclosed by the center in accordance with a request from the fourth device, and transmitting them to a later mentioned first apparatus for multiplying a bivector by an integer, (c) a sixth device for randomly selecting an integer Nu, keeping the thus selected integer Nu secret, and transmitting the integer Nu to a later mentioned first apparatus for multiplying a bivector by an integer, (d) a first apparatus for multiplying a bivector by an integer, for receiving the bivector Q and the parameter A from the third device, receiving the integer Nu from the sixth device, and calculating a bivector Qu by multiplying the bivector Q by the integer Nu, (e) a seventh device for receiving the bivector Qu from the first apparatus, and transmitting the bivector Qu to the center for disclosing as a public key, (f) a second apparatus for selecting a random number Ru and keeping the thus selected random number Ru secret, and transmitting the random number Ru to the first apparatus, the first apparatus receiving the bivector Q transmitted from the second device, the parameter A, and the random number Ru stored in the second apparatus, and multiplying the bivector Q by the random number Ru to thereby have a bivector C1 as a cipher, and storing the thus made cipher in a first storage memory, the first apparatus receiving the public key Qv of other user terminals stored in the second device, the parameter A, and the random number Ru, stored in the second apparatus, and multiplying the bivector Qv by the random number Ru to thereby have a bivector T1, and transmitting the thus made bivector T1 to an eighth device, (g) an eighth device for calculating a sum t1 of first elements in each of groups included in the bivector T1, and making a cipher C2 to which a correspondence M is added, and (h) a ninth device for cooperating with the eighth device to transmit the ciphers C1 and C2 to other user terminals, the program causing a computer to act as the user terminal as a receiver, the user terminal including (a) a tenth device for receiving and retaining the ciphers C1 and C2 transmitted from the user terminals as a transmitter, the first device receiving the cipher C1, an integer Nv retained in the sixth device, and the parameter A, and calculating a bivector T2 by multiplying the bivector C1 by the integer Nv, and (b) an eleventh device for receiving the cipher C2 and the bivector T2, calculating a sum t2 of first elements in each of groups included in the bivector T2, and decrypting the correspondence M by subtracting the sum t2 from the cipher C2.
There is further provided an El-Gamal type signature system wherein a parameter A defining a curve, and a bivector Q including a plurality of pairs of elements selected from a predetermined finite field are in advance informed of to all users, a certifier terminal U randomly selects an integer Nu as a signature key, and keeps the thus selected integer Nu secret, the certifier terminal U discloses a bivector Qu (Qu=Nuxc3x97Q) as a verification key, the bivector Qu being obtained by multiplying the bivector Q by the integer Nu, the certifier terminal U makes a signature text for a correspondence M through the use of any integer and the signature key Nu, and transmits the thus made signature text to a verification terminal V together with the correspondence M, and the verification terminal V verifies the correspondence M through the use of the signature text and the verification key Qu of the certifier terminal U.
There is further provided an El-Gamal type signature system including a center and a plurality of certifier terminals and verifier terminals, the center including (a) a first device for receiving verification keys disclosed by the certifier terminals, (b) a second device for receiving a request from one of the certifier and verifier terminals to transmit a bivector Q including a plurality of pairs of elements selected from a predetermined finite field, a parameter A defining a curve, and a verification key Qu, and (c) a third device for disclosing the bivector Q, the parameter A, and the verification key Qu to the one of the certifier and verifier terminals making the request, when the second device receives the request, the certifier terminal including (a) a fourth device for requesting the center to transmit the bivector Q and the parameter A, (b) a fifth device for receiving and retaining the bivector Q and the parameter A which have been disclosed by the center in accordance with a request from the fourth device, and transmitting them to a later mentioned first apparatus for multiplying a bivector by an integer, (c) a sixth device for randomly selecting an integer Nu, keeping the thus selected integer Nu secret as a signature key, and transmitting the signature key Nu to a later mentioned first apparatus for multiplying a bivector by an integer, (d) a first apparatus for multiplying a bivector by an integer, for receiving the bivector Q and the parameter A from the second device, receiving the signature key Nu from the sixth device, and calculating a bivector Qu by multiplying the bivector Q by the integer Nu, (e) a seventh device for receiving the bivector Qu from the first apparatus, and transmitting the bivector Qu to the center for disclosing as a verification key, (f) a second apparatus for selecting a random number K, keeping the thus selected random number K secret, and transmitting the random number K to the first device, the first device receiving the bivector Q and the parameter A transmitted from the second device, and the random number K stored in the second apparatus, multiplying the bivector Q by the random number K to thereby have a bivector R as a signed text, and storing the signed text R in an eighth device, (g) a ninth device for receiving a correspondence M, the signed text R (R=kxc3x97Q) from the first apparatus, the random number K from the second apparatus, and the signature key Nu from the sixth device, and calculating S (S=(Mxe2x88x92Nuxc3x97x(R))Kxe2x88x921 mod O(Q), wherein x(R) indicates a sum of first elements in each of groups included in a bivector R, and O(Q) indicates an order of the bivector Q) as a signed text, the signed text R, the signed text S, and the correspondence M being transmitted to the verifier terminal from the eighth, tenth and ninth devices, the verifier terminal including (a) an eleventh device for requesting the center to transmit the bivector Q, the parameter A, and the verification key all of which have been disclosed, (b) a twelfth device for receiving and retaining the bivector Q, the parameter A, and the verification key Qu, and transmitting them to a later mentioned third apparatus for multiplying a bivector by an integer, (c) a third apparatus for multiplying a bivector by an integer, the third apparatus receiving the bivector Q, the parameter A, and the correspondence M, calculating Mxc3x97Q by multiplying the bivector Q by the M to thereby have a bivector T1 as a result, and storing the thus calculated bivector T1 in a first storage memory, the third apparatus receiving a sum x(R) of first elements in each of groups included the bivector R having been received from the eighth device, receiving the verification key Qu and the parameter A from the twelfth device, calculating x(R)xc3x97Qu to thereby have a bivector T2 as a result, and storing the thus calculated bivector T2 in second storage device, the third apparatus receiving the bivector R, the signed text S, and the parameter A, calculating Sxc3x97R by multiplying the bivector R by the S to thereby have a bivector R3 as a result, and storing the bivector T3 in third storage device, (d) a fourth apparatus for summing bivectors, the fourth apparatus receiving the bivectors T2 and T3, and the parameter A, calculating (T2+T3) to thereby have a bivector T4 as a result, and storing the thus calculated bivector T4 in a fourth storage memory, and (e) a verification device for confirming whether the bivector T1 stored in the first storage memory is identical with the bivector T4 stored in the fourth storage memory, to thereby verify whether the correspondence M is made by the certifier terminal U.
There is further provided a recording medium readable by a computer, storing a program therein for accomplishing an El-Gamal type signature system including a center and a plurality of certifier terminals and verifier terminals, the program causing a computer to act as the center including (a) a first device for receiving verification keys disclosed by the certifier terminals, (b) a second device for receiving a request from one of the certifier and verifier terminals to transmit a bivector Q including a plurality of pairs of elements selected from a predetermined finite field, a parameter A defining a curve, and a verification key Qu, and (c) a third device for disclosing the bivector Q, the parameter A, and the verification key Qu to the one of the certifier and verifier terminals making the request, when the second means receives the request, the program causing a computer to act as the certifier terminal including (a) a fourth device for requesting the center to transmit the bivector Q and the parameter A, (b) a fifth device for receiving and retaining the bivector Q and the parameter A which have been disclosed by the center in accordance with a request from the fourth device, and transmitting them to a later mentioned first apparatus for multiplying a bivector by an integer, (c) a sixth device for randomly selecting an integer Nu, keeping the thus selected integer Nu secret as a signature key, and transmitting the signature key Nu to a later mentioned first device for multiplying a bivector by an integer, (d) a first apparatus for multiplying a bivector by an integer, for receiving the bivector Q and the parameter A from the second device, receiving the signature key Nu from the sixth device, and calculating a bivector Qu by multiplying the bivector Q by the integer Nu, (e) a seventh device for receiving the bivector Qu from the first apparatus, and transmitting the bivector Qu to the center for disclosing as a verification key, (f) a second apparatus for selecting a random number K, keeping the thus selected random number K secret, and transmitting the random number K to the first apparatus, the first apparatus receiving the bivector Q and the parameter A transmitted from the second device, and the random number K stored in the second apparatus, multiplying the bivector Q by the random number K to thereby have a bivector R as a signed text, and storing the signed text R in an eighth device, (g) a ninth device for retaining a correspondence M therein, and (h) a tenth device for receiving the correspondence M from the tenth device, the signed text R (R=kxc3x97Q) from the first apparatus, the random number K from the second apparatus, the signature key Nu from the sixth device, and the correspondence M from the tenth device, and calculating S (S=(Mxe2x88x92Nuxc3x97x(R))Kxe2x88x921 mod O(Q), wherein x(R) indicates a sum of first elements in each of groups included in a bivector R, and O(Q) indicates an order of the bivector Q) as a signed text, the signed text R, the signed text S, and the correspondence M being transmitted to the verifier terminal from the eighth, tenth and ninth devices, the program causing a computer to act as the verifier terminal including (a) an eleventh device for requesting the center to transmit the bivector Q, the parameter A, and the verification key all of which have been disclosed, (b) a twelfth device for receiving and retaining the bivector Q, the parameter A, and the verification key Qu, and transmitting them to a later mentioned third apparatus for multiplying a bivector by an integer, (c) a third apparatus for multiplying a bivector by an integer, the third apparatus receiving the bivector Q, the parameter A, and the correspondence M, calculating Mxc3x97Q by multiplying the bivector Q by the M to thereby have a bivector T1 as a result, and storing the thus calculated bivector T1 in a first storage memory, the third apparatus receiving a sum x(R) of first elements in each of groups included the bivector R having been received from the eighth device, receiving the verification key Qu and the parameter A from the twelfth device, calculating x(R)xc3x97Qu to thereby have a bivector T2 as a result, and storing the thus calculated bivector T2 in second storage memory, the third apparatus receiving the bivector R, the signed text S, and the parameter A, calculating Sxc3x97R by multiplying the bivector R by the S to thereby have a bivector R3 as a result, and storing the bivector T3 in third storage memory, (d) a fourth apparatus for summing bivectors, the fourth apparatus receiving the bivectors T2 and T3, and the parameter A, calculating (T2+T3) to thereby have a bivector T4 as a result, and storing the thus calculated bivector T4 in fourth storage memory, and (e) a verification device for confirming whether the bivector T1 stored in the first storage memory is identical with the bivector T4 stored in the fourth storage memory, to thereby verify whether the correspondence M is made by the certifier terminal U.
The above and other objects and advantageous features of the present invention will be made apparent from the following description made with reference to the accompanying drawings, in which like reference characters designate the same or similar parts throughout the drawings.